from typing import List


class Solution:
    # 超时
    def isZeroArray1(self, nums: List[int], queries: List[List[int]]) -> bool:

        for a,b in queries:
            # range是左闭右开，所以b要加+1
            for i in range(a,b+1):
                if nums[i] == 0:
                    continue
                nums[i]-=1
                # print(nums)
        return not any(nums)
    # 剪枝也超时
    def isZeroArray2(self, nums: List[int], queries: List[List[int]]) -> bool:
        # 将所有范围先统计减的次数，超过0就不减了
        is_last = False
        for q_index in range(len(queries)):
            a,b = queries[q_index]
            if q_index == len(queries)-1:
                is_last =  True
            # range是左闭右开，所以b要加+1
            for i in range(a, b + 1):
                if nums[i] == 0:
                    continue
                nums[i] -= 1
                if is_last and nums[i] != 0:
                    return False
                # print(nums)
        return not any(nums)

    def isZeroArray3(self, nums: List[int], queries: List[List[int]]) -> bool:
        # 统计哪些下标需要减多少次
        fre = [0]*len(nums)
        for a,b in queries:
            for i in range(a,b+1):
                fre[i] += 1
        for index, f in enumerate(fre):
            dec = nums[index]- f
            if dec>0:
                return False
        return True

    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        deltaArray = [0] * (len(nums) + 1)
        for left, right in queries:
            deltaArray[left] += 1
            deltaArray[right + 1] -= 1
        operationCounts = []
        currentOperations = 0
        for delta in deltaArray:
            currentOperations += delta
            operationCounts.append(currentOperations)
        for operations, target in zip(operationCounts, nums):
            if operations < target:
                return False
        return True
nums = [4,3,2,1]
queries = [[1,3],[0,2]]
print(Solution().isZeroArray(nums, queries))